package com.lft.tree10.segment_tree;

/**
 * 前缀和
 */
public class PreSum {
	public static void main(String[] args) {
		int[] nums = {-2, 0, 3, -5, 2, -1};
		NumArray numArray = new NumArray(nums);
		System.out.println(numArray.sumRange(0, 2));
		System.out.println(numArray.sumRange(2, 5));
		System.out.println(numArray.sumRange(0, 5));
	}
}

class NumArray {
	//sum [i] 存储前 i 个元素的和
	private int[] sum;
	
	public NumArray(int[] nums) {
		sum = new int[nums.length + 1];
		sum[0] = 0;
		// 初始化 sum
		for (int i = 1; i < sum.length; i++) {
			sum[i] = sum[i - 1] + nums[i - 1];
		}
	}
	
	public int sumRange(int i, int j) {
		return sum[j + 1] - sum[i];
	}
}